package bintree.LeetCode;
//中序遍历非递归写法

import java.util.*;

//中序遍历非递归写法——借助栈
public class Num94_inorder_非递归 {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> rep = new ArrayList<>();//用动态数组保存数据
        if(root == null){
            return rep;//返回一个空数组
        }
        Deque<TreeNode> stack = new ArrayDeque<>();//链表形式的栈
        //stack.push(root);//这里先别着急入栈，不然下面while循环会多入栈一次
        TreeNode cur = root;//用cur记录是否左走到头
        //因为没有第一时间入栈，所以需要增加一个条件 cur ！= null
        while(cur != null || !stack.isEmpty()){
            //先一路向左走到 底
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }//此时出来后cur就是null了   //————左
            //说明cur该返回了，他的父类节点是第二次了
            cur = stack.pop();//出栈   //————跟
            rep.add(cur.val);//保存出栈的值

            cur = cur.right;//继续访问它的右子树，看看是否需要查询 //————右
        }

        return rep;
    }

}
